home *** CD-ROM | disk | FTP | other *** search
/ Delphi Magazine Collection 2001 / Delphi Magazine Collection 20001 (2001).iso / DISKS / Issue35 / alfresco / TwrHanoi.dpr < prev   
Encoding:
Text File  |  1998-05-26  |  3.9 KB  |  140 lines
  1. program TwrHanoi;
  2.  
  3. {$IFDEF Win32}
  4. {$APPTYPE CONSOLE}
  5. {$ENDIF}
  6.  
  7. uses
  8.   {$IFDEF Win32}
  9.   Windows,
  10.   {$ELSE}
  11.   WinCRT, WinTypes, WinProcs,
  12.   {$ENDIF}
  13.   SysUtils;
  14.  
  15. var
  16.   MoveCount : integer;
  17.  
  18. procedure StackHanoi(N : byte; FromPole, ToPole, SparePole : char);
  19. {move N disks from FromPole to ToPole using SparePole as a spare}
  20. type
  21.   TParam = record
  22.     pN : byte;
  23.     pFrom, pTo, pSpare : char;
  24.   end;
  25. var
  26.   Stack : array [0..127] of TParam;
  27.   SP    : integer;
  28.   P     : TParam;
  29. begin
  30.   {clear the stack}
  31.   SP := 0;
  32.   {push our parameters onto the stack}
  33.   with Stack[SP] do begin
  34.     pn := N; pFrom := FromPole; pTo := ToPole; pSpare := SparePole;
  35.   end;
  36.   inc(SP);
  37.   {while the stack is not empty...}
  38.   while (SP <> 0) do begin
  39.     {pop the stack}
  40.     dec(SP);
  41.     longint(P) := longint(Stack[SP]);
  42.     {if the disk number is 1, or it's a move, move it}
  43.     if (P.pN = 1) or (P.pSpare = #0) then begin
  44.       inc(MoveCount);
  45.       writeln('Move disk ', P.pN, ' from ', P.pFrom, ' to ', P.pTo);
  46.     end
  47.     else begin
  48.       {push the parameters to move N-1 disks from Spare to To}
  49.       with Stack[SP] do begin
  50.         pN := P.pN - 1;
  51.         pFrom := P.pSpare; pTo := P.pTo; pSpare := P.pFrom;
  52.       end;
  53.       inc(SP);
  54.       {push the parameters for the move}
  55.       with Stack[SP] do begin
  56.         pn := P.pN;
  57.         pFrom := P.pFrom; pTo := P.pTo; pSpare := #0;
  58.       end;
  59.       inc(SP);
  60.       {push the parameters to move N-1 disks from From to Spare}
  61.       with Stack[SP] do begin
  62.         pn := P.pN - 1;
  63.         pFrom := P.pFrom; pTo := P.pSpare; pSpare := P.pTo;
  64.       end;
  65.       inc(SP);
  66.     end;
  67.   end;
  68. end;
  69.  
  70. procedure FastHanoi(N : integer; FromPole, ToPole, SparePole : char);
  71. {move N disks from FromPole to ToPole using SparePole as a spare}
  72. var
  73.   Finished : boolean;
  74.   Temp : char;
  75. begin
  76.   Finished := false;
  77.   while not Finished do begin
  78.     {if there's just one disk, move it}
  79.     if (N = 1) then begin
  80.       inc(MoveCount);
  81.       writeln('Move disk ', N, ' from ', FromPole, ' to ', ToPole);
  82.       Finished := true;
  83.     end
  84.     else {move more than one disk} begin
  85.       {First: move N-1 disks to SparePole, using ToPole as the spare}
  86.       FastHanoi(N-1, FromPole, SparePole, ToPole);
  87.       {Second: move the Nth disk}
  88.       inc(MoveCount);
  89.       writeln('Move disk ', N, ' from ', FromPole, ' to ', ToPole);
  90.       {Last: move N-1 disks from SparePole to ToPole, using FromPole as
  91.        the spare}
  92.       dec(N);
  93.       Temp := SparePole;
  94.       SparePole := FromPole;
  95.       FromPole := Temp;
  96.     end;
  97.   end;
  98. end;
  99.  
  100. procedure Hanoi(N : integer; FromPole, ToPole, SparePole : char);
  101. {move N disks from FromPole to ToPole using SparePole as a spare}
  102. begin
  103.   {if there's just one disk, move it}
  104.   if (N = 1) then begin
  105.     inc(MoveCount);
  106.     writeln('Move disk ', N, ' from ', FromPole, ' to ', ToPole);
  107.   end
  108.   else {move more than one disk} begin
  109.     {First: move N-1 disks to SparePole, using ToPole as the spare}
  110.     Hanoi(N-1, FromPole, SparePole, ToPole);
  111.     {Second: move the Nth disk}
  112.     inc(MoveCount);
  113.     writeln('Move disk ', N, ' from ', FromPole, ' to ', ToPole);
  114.     {Last: move N-1 disks from SparePole to ToPole, using FromPole as
  115.      the spare}
  116.     Hanoi(N-1, SparePole, ToPole, FromPole);
  117.   end;
  118. end;
  119.  
  120. var
  121.   EndTime, StartTime : integer;
  122.   DiskCount : integer;
  123.   AvePerMove : double;
  124.  
  125. begin
  126.   MoveCount := 0;
  127.   DiskCount := 10;
  128.   StartTime := GetTickCount;
  129.   StackHanoi(DiskCount, 'A', 'B', 'C');
  130.   EndTime := GetTickCount;
  131.   writeln('Number of disks: ', DiskCount);
  132.   writeln('Number of moves: ', MoveCount);
  133.   writeln('Time taken: ', EndTime - StartTime);
  134.   AvePerMove := (EndTime - StartTime) / MoveCount;
  135.   writeln('Average milliseconds per move: ', AvePerMove:15:9);
  136.   writeln('Time in years to do 64 disks: ', AvePerMove * 1.844674407371e+19 /
  137.                                    (1000 * 60 * 60 * 24 * 365.25):15:5);
  138.   readln;
  139. end.
  140.